The present invention relates to a method of and a system for managing shared resources, and more particularly to a shared resource management technique in which access to a large quantity of shared resource elements as the object of management between processes to be subjected to parallel processing is serialized under a multiprocessing environment or a multiprogramming environment on an electronic computer.
In general, a serialization of access to a shared resource is realized by a series of instructions called "lock" and "unlock" operations and is usually provided as one function of an operating system (OS). In this access control method, when collision on access occurs, the processing by any process other than a locked process is interrupted and the other process is brought into a waiting condition. However, such an interruption causes an excess overhead of the system on several occasions, especially, under a tightly-coupled multiprocessor environment where a main storage (MS) is shared by a plurality of instruction processors.
A method of realizing the serialization of access between processes subjected to parallel processing with no lock operation is disclosed by, for example, U.S. Ser. No. 787221 filed Oct. 15, 1985, now U.S. Pat. No. 4,847,754 (JP-A-62-92061). In the above-referenced method, when collision on access between processes is present, the processing by any one of processes in collision with each other is transferred and entrusted to the other of those processes. According to this method, it is possible to perform the retrieval, registration and/or deletion of data elements for a list of data on a main storage with no interruption of any process.
The above-mentioned prior art is mainly directed to a one-dimensional list structure in which data are linked by a pointer chain. Such a data list is suitable for sequential retrieval or direct retrieval in the case where the number of elements is small. However, the retrieval overhead increases linearly with respect to the number of elements. Therefore, in the case where random access to a large quantity of elements occurs, it does not necessarily follow that such a data list is an optimum data structure.
A preferable data structure suitable for the case where random access to a large quantity of elements occurs is one for which a hashing method as high-speed retrieval means can be used. However, the above-mentioned prior art in which the processing by one process is entrusted to the other process, is not applicable to a data structure which uses a hashing method.